//*************************************************
//Program #4       SCA.cpp
//*************************************************
//Names: Stephen Durfrey,  Andrew Brock
//Due: April 23, 2010
//Operating Systems
//Related Files:  SCA.h
// Second-Chance PGA: FIFO-like algorithm with a second chance
//  to "survive" in memory.


#include "SCA.h"
#include <vector>
#include <string>
#include <stdlib.h>
#include <algorithm>

using namespace std;
//Default Constructor
SCA::SCA()
{
}
//*************************************************
//SCA::init - initializes the varibles based on the variables
// passed into the program.
//*************************************************
void SCA::init(int frames, vector<int> ref_str)
{
	num_frames = frames;
	ref_string = ref_str;
	num_faults = 0;
	ref_page = ref_string.begin();
}
//*************************************************
//SCA::checkFrame - checks to see if the value "check"
// is in the frames.  If it is its location is passed back
// otherwise check == frames.end()
//*************************************************
vector<int>::iterator SCA::checkFrame(vector<int>::iterator check)
{
	bool found = false;
	vector<int>::iterator value, begin, end;

	value = end = frames.end();

	for(begin = frames.begin(); begin != end && !found; begin++)
	{
		if(*begin == *check)
		{
			value = begin;
			found = true;
		}
	}

	return value;

}
//*************************************************
//SCA::removePage - this is where the loop is that the SCA
// page replacement algorithm is tested.
//*************************************************
void SCA::removePage()
{
	
	vector<int>::iterator begin, end, pos, position;
	end = ref_string.end();
	ref_page = ref_string.begin();
	bool foundVictim = false;

	do
	{//BEGIN DO-WHILE
		if(frames.size() != num_frames)
		{//BEGIN IF
			//First checks to see if ref_page is already in the frames
			position = checkFrame(ref_page);
			if(position == frames.end())
			{//Frames has an empty slot
				frames.push_back(*ref_page);
				num_faults++;
				//sets its second chance to true
				secondChance.push_back(1);
			}
		}//END IF
		else
		{//BEGIN ELSE
			begin = frames.begin();
			ref_secChan = secondChance.begin();
			
			//check to see if the ref_page currently exists in the set of frames
			pos = find(frames.begin(), frames.end(), *ref_page);

			//if it doesn't exist, run second-chance algorithm
			if(pos == frames.end())
			{//BEGIN IF
				while(!foundVictim)//BEGIN WHILE
				{
					//Checks if a frame has a second chance.
					if(*ref_secChan == 1)
					{
						//If it does remove it
						if(*ref_page == *begin)
							foundVictim = true;						
						else
							*ref_secChan = 0;
					}
					//Otherwise either find it in the frames and set its
					// second chance to true.  Or replace the value if it
					// isn't in the frames.
					else
					{
						if(*ref_page == *begin)
						{
							foundVictim = true;
							*ref_secChan = 1;
						}
						else
						{
							*begin = *ref_page;
							*ref_secChan = 1;
							foundVictim = true;
							num_faults++;
						}
					}
					//If the iterator that goes through frames is at the end
					// set it back to start.
					if((begin + 1) == frames.end())
					{
						ref_secChan = secondChance.begin();
						begin = frames.begin();
					}
					else
					{
						begin++;
						ref_secChan++;
					}
				}//END WHILE
			}//END IF
		}//END ELSE

		foundVictim = false;
		ref_page++;


	}while(ref_page != end);//END DO-WHILE
}
//*************************************************
//SCA::run - executes the algorithm and then outputs
// the results of values num_frames and num_faults
//*************************************************
void SCA::run()
{
	char value[50];
	string value_param;
	removePage();

	sprintf(value, "%d , %d", num_frames, num_faults);

	value_param = (string)value;
	addCsvString("SCA.txt", value_param );
}

